home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 16303 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: seagoon.newcastle.edu.au!usenet
  2. From: mazz@faceng.newcastle.edu.au (Richard Mazzaferri)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Fastest Sorting Algorithm?
  5. Date: Wed, 10 Apr 1996 09:16:03 GMT
  6. Organization: Newcastle University
  7. Message-ID: <316b7b66.13881382@news.newcastle.edu.au>
  8. References: <Dou55w.7MB@novice.uwaterloo.ca> <DpAxtI.3w9@undergrad.math.uwaterloo.ca> <4k4unk$15qe@sol.caps.maine.edu> <4k680p$6fs@longwood.cs.ucf.edu> <4k6hdg$5ob@blackice.winternet.com>
  9. NNTP-Posting-Host: tesla.newcastle.edu.au
  10.  
  11. jdege@winternet.com (Jeff Dege) wrote:
  12.  
  13. > On 6 Apr 1996 12:01:13 -0500, Mark Schnitzius (schnitzi@longwood.cs.ucf.edu) wrote:
  14. > : 
  15. > : Is it really 2logn?  My understanding was that a sort couldn't be
  16. > : less than nlogn...  More info, please.
  17.  
  18. >     No sort that works on comparing elements can be less than O(n*log(n)).
  19.  
  20. You should probably add modify that statement to "No sort on a serial
  21. architecture that works on comparing elements..." before parallel
  22. processing afficionados jump into the fray :-)
  23.  
  24. *Any* sorting algorithm on a serial architecture must take at least O(n)
  25. because it has to process each input element at least once.  So, the
  26. claimed sorting algorithm running in O(2log n) must be running on a
  27. parallel architecture - which is probably not of any use to the author of
  28. the original question.
  29.  
  30. > trickSort(int A[], int size)
  31. > {
  32. >     int i;
  33. > 
  34. >     for (i=0; i<size; i++)
  35. >         A[0] = 0;
  36. > }
  37.  
  38. Which of course (disregarding the fact that the algorithm fails to sort its
  39. inputs at all) is O(n) - much slower than the claimed O(2log n) algorithm
  40. :-)
  41.  
  42. Have fun,
  43.     Mazz.
  44. mazz@faceng.newcastle.edu.au
  45.